package algorithm;

import java.util.Arrays;
import java.util.LinkedList;

public class T00239 {
    public static void main(String[] args) {
        int[] nums = {-7,-8,7,5,7,1,6,0};
        int k = 4;
        System.out.println(Arrays.toString(new Solution().maxSlidingWindow(nums, k)));
    }

    static class Solution {

        public int[] maxSlidingWindow(int[] nums, int k) {
            Window window = new Window(nums);
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i < nums.length; i ++) {
                if (i < k - 1) {
                    window.push(i);
                } else if (i == k - 1) {
                    window.push(i);
                    res[i - k + 1] = nums[window.max()];
                } else {
                    window.push(i);
                    window.poll(i - k);
                    res[i - k + 1] = nums[window.max()];
                }
            }
            return res;
        }

        public static class Window {

            private final int[] nums;

            private LinkedList<Integer> list = new LinkedList<>();

            public Window(int[] nums) {
                this.nums = nums;
            }

            public void push(int n) {
                while (!list.isEmpty() && nums[list.getLast()] <= nums[n]) {
                    list.pollLast();
                }
                list.offerLast(n);
            }

            public int max() {
                return list.getFirst();
            }

            public void poll(int n) {
                if (list.getFirst() == n) {
                    list.pollFirst();
                }
            }
        }
    }
}
